In the basic computer system, a central processing unit or processor is operative in accordance with a predetermined program or set of instructions stored within an associated memory. In addition to the stored instruction set or program under which the processor operates, memory space either within the processor memory or in an associated additional memory, is provided to facilitate the central processors manipulation of information during processing. In essence, the additional memory provides for the storage of information created by the processor as well as the storage of information on a temporary or "scratchpad" basis which the processor uses on an interim basis in order to carry out the program. In addition, the associated memory often provides locations in which the output information of the processor operating under the program set may be placed in order to be available for the system's output device. For example, once the processor has produced a predetermined table of information, it may be formatted and stored within the additional memory to facilitate its display on the system monitor or its transmission to a printer for hard copy output.
In the systems of the type described above in which a single processor is operative and utilizes one or more associated memories, the access of the processor to the different memories is relatively simple and straight forward. However, in more complex computer systems in which two processors or in which systems utilizing different processors are simultaneously in operation, access to memory becomes more complex. Since it is likely that each of the processors or processor systems may require access to the same memory simultaneously, a conflict between processors will generally be unavoidable. In essence, the operation of two processors or processor systems periodically results in overlap of the processors with respect to a common memory. Such overlap may, in some systems, be eliminated by complete redundancy of the memories used for each of the processors and isolation of the two processor systems. However, this often defeats the intended advantage of the multiple processor system. Such multiple processor systems are most efficient if operative to simultaneously carry forward multiple computing operations upon the same data in which one processor supports the operation of the other. Such dual processor systems may be either time shared in which the processors compete for access to a common bus or dual ported in which each processor has its own memory bus and one is queued while the other is given access.
A similar problem of conflicting memory access demands often arises in systems in which a plurality of users require access to a common data base. These systems are often referred to as "multiuser" systems. Because the data base sought to be used is nothing more than a common memory, the overlap of processor use created by simultaneous attempts of two or more processors to access the same data base is again likely to occur.
With the onset of the memory foregoing types of access problem, practitioners in the art have sought, by system architecture, to either avoid conflicts entirely (conflict avoidance) or to set up various systems which sense the existence of conflicts between processors and resolve them in accordance with some predetermined set of system rules (priority system). The avoidance of conflict is a very basic system approach in which the processors are sequentially operated or operated on a time sharing base. In essence, the processors simply "take turns". One of the most common sequential conflict avoidance systems is that known as "passing the ring" or "token system" in which the potentially conflicting processors are simply polled by the system in accordance with a predetermined sequence similar to passing a ring about a group of users.
While conflict avoidance, through the use of sequenced processor access, provides a solution to conflicting processor access demands upon a common memory, its use imposes a significant limitation upon the operation of the overall computing system. This limitation arises from the fact that a substantial time is used by the system in polling the competing processors in accordance with the sequence. In the event a single processor is operating and requires access to the common memory, a delay between processor accesses to the memory is created following each memory cycle as the system steps through the sequence.
As a result of the shortcomings and system limitations associated with the conflict avoidance approach using sequential processor access, practitioners in the art have created various priority systems in which the conflicts of competing processors are resolved on the basis of some preestablished priority. In the simplest such system, each processor is assigned a priority within the hierarchy of system importance and the memory controller simply provides access to the highest priority processor each time a conflict occurs. All lower priority processors simply wait for access to the memory. For example, in a typical two processor system, a first and a second processor are operative and access a common memory. In addition, the type of the memory most often used is known as a dynamic RAM or DRAM which requires periodic refreshing of the memory to maintain the stored data. Generally, the memory is refreshed by a separate independent refresh system which includes means for timing the refresh interval. In such a system, both processors and the refresh system compete for access to the common memory. While each system is different, the likely priority to be assigned will place the refresh system at the highest priority and then based upon system architecture, a higher priority is assigned to one of the processors over the other. For example, the system may determine that the highest priority will be given to the first processor and a lower priority given to the second processor. As a result, the system will function normally in the absence of conflict. Each time a request to access the common memory is received by the memory controller. It will grant the request and the processor will access the memory. If however, simultaneous requests are received by the controller, a conflict arises and the controller will grant access first to the refresh system. If no refresh request exists, it will grant access to the first processor. After the refresh and/or the first processor are finished and if neither makes another request, access to the second processor is granted. While such systems resolve the conflict of simultaneous requests and provide a more efficient operation than a purely sequential conflict avoidance system, straight priority systems suffer from a lack of flexibility. As a result, they cannot meet varying circumstances in which the priorities of the competing memory access must be changed to meet a given situation. For example, it may be that one processor is the dominant and "most important" processor in the system in most computing operations. However, there invariably arise circumstances in which it is nonetheless desirable to grant a higher priority to the second processor in order to smooth out overall system speed and performance. As a result, the straight priority system is a relatively fast system, in the sense that no time is allocated to a decision making process and therefore a request may be granted by the controller relatively quickly. However, overall system speed may be lost as a processor with a lower assigned priority waits for access to complete an essential function.
This need for flexibility in the priority assignment, has prompted practitioners in the art to create systems with actual decision making capability incorporated within the system of the memory controller. While a number of such decision making memory controllers have been produced and they vary somewhat in specific operation, generally all provide a sequential decision making process which is carried forward each time simultaneous requests are made. Unfortunately, because the decision making portions of the memory controller are operated under the control and timing of a clock system, a problem arises in that considerable time may be utilized in going through the deicsion process before the memory controller can grant access to a particular processor. While a simple solution would involve increasing the speed of the clock under which the memory controller is operating, there arises a general limitation on the practical speed of such clock circuits within economically feasible production devices. As a result, as system designers create faster and faster central processing units, a basic dilemma arises in designing memory controllers. On the one hand, there is a need for increased decision making capability or intelligence. On the other hand, there is a need for increased speed of operation in granting memory access. Unfortunately, it appears that at present, each of these needs tends to exclude the other. In other words, at some point, increased memory controller intelligence or decision making capability is achieved at a reduction of overall speed of request processing and conversely system design characteristics targeted at increasing the speed of request processing by the memory controller are achieved at a sacrifice of the intelligence or decision making flesibility of the memory controller.
There arises therefore a need in the art for a memory controller capable of controlling the access to a common memory between two competing processor or processor systems in which the memory controller operates with sufficient speed to grant the processor access requests while maintaining sufficient system flexibility to maintain the overall speed of the multiple processor computing system.